package astudy.tree.impl;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 线段树的实现
 *  
 * @author Administrator
 *
 */
public class SegmentTree {

	private Node root;
	
	public static class Node {
		
		int start;
		int end;
		int count;
		Node left;
		Node right;
		int m;		
	
		public Node(int start, int end) {
			this.start = start;
			this.end = end;
			this.count = 0;
			this.left = null;
			this.right = null;
		}
		
		public String toString() {
			return "[" + start + "," + end + "]{" + count + "}";
		}

		public int getStart() {
			return start;
		}

		public void setStart(int start) {
			this.start = start;
		}

		public int getEnd() {
			return end;
		}

		public void setEnd(int end) {
			this.end = end;
		}
	}

	public SegmentTree() {
		this.root = null;
	}
	
	public SegmentTree(int start, int end) {
		this.root = new Node(start, end);
	}
	
	public String toString() {

		String s = "";
		LinkedList<Node> nodes = new LinkedList<Node>();
		nodes.add(this.root);
		Node node = nodes.poll();
		while (node != null) {
			if (node.left != null) {
				nodes.add(node.left);
			}
			if (node.right != null) {
				nodes.add(node.right);
			}
			s += node.toString() + " ";
			node = nodes.poll();
		}
		return s;
	}
	
	public Node build(int start, int end) {
		
		Node node = new Node(start, end);
		if (start+1 < end) {
			int m = (start + end)/2;
			node.left = build(start, m);
			node.right = build(m, end);
		} else {
			node.left = null;
			node.right = null;
		}
		return node;
	}
	
	public void insert(int start, int end) {
		if (start >= end) {
			throw new RuntimeException();
		}
		insert(root, start, end);
	}

	/**
	 * 注意几点：
	 * Note 01. 
	 * 
	 * 
	 * @param node
	 * @param start
	 * @param end
	 */
	private void insert(Node node, int start, int end) {
		
		int m = (node.start + node.end)/2;
		if (node.start == start && node.end == end) {
			node.count ++;
		} else if (end <= m) {
			//Note 01. 为了提高程序的可用性，减少内存和创建SegmentTree的时间，
			//所有节点只有在必要的时候才会创建。
			if (node.left == null) {
				node.left = new Node(node.start, m);
			}
			insert(node.left, start, end);
		} else if (start >= m) {
			if (node.right == null) {	//Note 01
				node.right = new Node(m, node.end);
			}
			insert(node.right, start, end);
		} else {
			if (node.left == null) {	//Note 01
				node.left = new Node(node.start, m);
			}
			insert(node.left, start, m);
			if (node.right == null) {	//Note 01
				node.right = new Node(m, node.end);
			}
			insert(node.right, m, end);
		}
		
		//Note 02. 每次增加一个节点，便更新他的度量属性(node.m)
		updateM(node);
	}
	
	public void delete(int start, int end) {
		delete(root, start, end);
	}

	/**
	 * 与insert非常类似
	 * 
	 * @param node
	 * @param start
	 * @param end
	 */
	private void delete(Node node, int start, int end) {
		
		int m = (node.start + node.end)/2;
		if (node.start == start && node.end == end) {
			node.count --;
		} else if (end <= m) {
			delete(node.left, start, end);
		} else if (start >= m) {
			delete(node.right, start, end);
		} else {
			delete(node.left, start, m);
			delete(node.right, m, end);
		}
		
		updateM(node);
		if (node.count == 0) {	//Note 01. 释放无用节点
			node = null;
		}
	}
	
	public int length() {
		return this.root.m;
	}
	
	private void updateM(Node node) {
        if (node.count > 0) {// 被覆盖满
        	node.m = node.end-node.start;
		} else if (node.end - node.start == 1) {// 该节点为叶节点
			node.m = 0;
        } else {// 其他内部节点的情况
        	int lm = (node.left == null)?0:node.left.m;
        	int rm = (node.right == null)?0:node.right.m;
        	node.m = lm + rm;
        }
	}
	
	public List<Node> segments() {
		List<Node> nodeList = segments(this.root);
		List<Node> nodes = new ArrayList<Node>();
		
		if (nodeList.size() == 0) {
			return nodes;
		} else {
			int l = -1, r = -1;
			for (int i = 0; i < nodeList.size(); i ++) {
				int tmpL = nodeList.get(i).start;
				int tmpR = nodeList.get(i).end;
				if (i == 0) {
					l = tmpL;
					r = tmpR;
				} else if (r == tmpL ) {
					r = tmpR;
				} else {
					nodes.add(new Node(l, r));
					l = tmpL;
					r = tmpR;
				}
			}
			nodes.add(new Node(l, r));
			return nodes;
		}
	}
	
	private List<Node> segments(Node node) {

		List<Node> nodes = new ArrayList<Node>();
		if (node == null) {
			
		} else if (node.count > 0) {
			nodes.add(node);
		} else {
			nodes.addAll(segments(node.left));
			nodes.addAll(segments(node.right));
		}
		return nodes;
	}
}
